package 热题100;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class 热题36有效的数独 {

    /*
    数字 1-9 在每一行只能出现一次。
    数字 1-9 在每一列只能出现一次。
    数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
     */

    public boolean isValidSudoku(char[][] board) {
        /*
        rol:1-9行中每一行包含的数
        col：1-9列中，每一列包含的数
        area：每一个小方格中包含的数，方格的编号计算：hang / 3 * 3 + lie / 3
         */
        Map<Integer,Set> rol = new HashMap<>(),col = new HashMap<>(),area = new HashMap<>();

        for (int i = 0; i < 9; i++) {
            rol.put(i,new HashSet());//将每行的下标保存在map的key中
            col.put(i,new HashSet());
            area.put(i,new HashSet());
        }
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c == '.') continue;
                int val = c - 0;
                int index = i / 3 * 3 + j / 3;
                //如果行列方格中包含，那么就直接返回false
                if (rol.get(i).contains(val) || col.get(j).contains(val) || area.get(index).contains(val)) {
                    return false;
                }
                //否则添加
                rol.get(i).add(val);
                col.get(j).add(val);
                area.get(index).add(val);
            }
        }
        //遍历结束后返回，说明数独合法，退出
        return true;
    }



    public boolean isValidSudoku1(char[][] board) {
        //定义三个boolean数组，默认为false
        boolean[][] row = new boolean[10][10], col = new boolean[10][10], area = new boolean[10][10];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                int c = board[i][j];
                if (c == '.') continue;
                int u = c - '0';
                int idx = i / 3 * 3 + j / 3;
                //如果数组中的数，第一次出现，那么就继续将当前行的第 u 个位置置为true，
                if (row[i][u] || col[j][u] || area[idx][u]) return false;
                row[i][u] = col[j][u] = area[idx][u] = true;
            }
        }
        return true;
    }
}
